package com.lagou;

/**
 * @author: lcz
 * @date: Created in 9:41 2021/4/23
 * @description: 很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不 同。
 * 例如有的金矿储量是500kg黄金，需要5个工人来挖掘；有的金矿储量是200kg黄金，需要3个工人 来挖掘…… 如果参与挖矿的工人的总数是10。
 * 每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。要求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
 */
public class SeniorPractice {

    public static void main(String[] args) {
        int w = 10;
        int[] p = {5, 5, 3, 4, 3};
        int[] g = {400, 500, 200, 300, 350};
        System.out.println("最优收益：" + getBestGoldMining(w, g.length, p, g));
    }

    /**
     * 获得金矿最优收益
     * @param w 工人数量
     * @param n 可选金矿数量
     * @param p 金矿开采所需的工人数量
     * @param g 金矿储量
     *  把金矿数量设为n，工人数量设为w，金矿的含金量设为数组g[]，金矿所需开采人数设为数组p[]. 设F(n, w)为n个金矿、w个工人时的最优收益函数，那么状态转移方程式如下
     *  F(n,w) = 0 (n=0或w=0)
     * 问题边界，金矿数为0或工人数为0的情况
     * F(n,w)= F(n-1,W) (n≥1, w<p[n-1])
     * 当所剩工人不够挖掘当前金矿时，只有一种最优子结构
     * F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n≥1, w≥p[n-1])
     * 在常规情况下，具有两种最优子结构(挖当前金矿或不挖当前金矿)
     */
    public static int getBestGoldMining(int w, int n, int[] p, int[] g) {
        if (w == 0 || n == 0) {
            return 0;
        }
        if (w < p[n - 1]) {
            return getBestGoldMining(w, n - 1, p, g);
        }
        return Math.max(getBestGoldMining(w, n - 1, p, g), getBestGoldMining(w - p[n - 1], n - 1, p, g) + g[n - 1]);
    }

}
